#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <map>
#include <bitset>
#include <list>
#include "common.h"
using namespace std;

class labelInfo{
public:
    string label;
    unsigned posInGlobal;
    unsigned instanceCount;
};
class subPartVid{
public:
    list<unsigned> subpart;
    unsigned vid;
};
class subPartInfo{
public:
    unsigned len;
    unsigned svid;
    unsigned evid;
    unsigned prelen;
    unsigned index;
};
uint32_t MurmurHash2(const void * key, int len, uint32_t seed)
{
    // 'm' and 'r' are mixing constants generated offline.
    // They're not really 'magic', they just happen to work well.
    const uint32_t m = 0x5bd1e995;
    const int r = 24;
    // Initialize the hash to a 'random' value
    uint32_t h = seed ^ len;
    // Mix 4 bytes at a time into the hash
    const unsigned char * data = (const unsigned char *) key;
    while (len >= 4) 
    {
        uint32_t k = *(uint32_t*) data;
        k *= m;
        k ^= k >> r;
        k *= m;
        h *= m;
        h ^= k;
        data += 4;
        len -= 4;
    }
    // Handle the last few bytes of the input array
    switch (len) 
    {
        case 3:
            h ^= data[2] << 16;
        case 2:
            h ^= data[1] << 8;
        case 1:
          h ^= data[0];
          h *= m;
    };
    // Do a few final mixes of the hash to ensure the last few
    // bytes are well-incorporated.
    h ^= h >> 13;
    h *= m;
    h ^= h >> 15;
    return h;
}
void extractEUINT(string &line, unsigned *e_info){
    int start = 0,len=0,i=0;
    int count=0;
    while(i<line.length()){
        if(line[i]>='0' && line[i]<='9'){
            start = i;
            len=0;
            while(i<line.length()){
                if(line[i]>='0' && line[i]<='9'){
                    len++;
                }else{
                    break;
                }
                i++;
            }
            string temp = line.substr(start,len);
            e_info[count] = stoul(temp);
            count++;
            if(count==3)
                break;
        }
        i++;
    }
}
void extractUINT(string &line, map<unsigned,unsigned>&v_label,unsigned &v_num){
    int start = 0,len=0,i=0,vid,lid;
    while(i<line.length()){
        if(line[i]>='0' && line[i]<='9'){
            start = i;
            while(i<line.length()){
                if(line[i]>='0' && line[i]<='9'){
                    len++;
                }else{
                    break;
                }
                i++;
            }
            break;
        }
        i++;
    }
    string temp = line.substr(start,len);
    vid = stoul(temp);
    len=0;
    while(i<line.length()){
        if(line[i]>='0' && line[i]<='9'){
            start = i;
            while(i<line.length()){
                if(line[i]>='0' && line[i]<='9'){
                    len++;
                }else{
                    break;
                }
                i++;
            }
            break;
        }
        i++;
    }
    temp = line.substr(start,len);
    lid = stoul(temp);
    if(vid+1>v_num){
        v_num=vid+1;
    }
    v_label.insert(pair<unsigned,unsigned>(vid,lid));
}

bool sortFuncUINT(unsigned m1, unsigned m2){
    return m1 < m2;
}

class Node{
public:
    vector<Node*> children;
    Node *parent;
    int subPartID;
    uint16_t groupid;
    uint16_t elpmap;
    int elpNum;
};
uint16_t returnLow1(uint16_t a)
{
    uint16_t n = a&(~a+1);
	return n;
}
int CountOnes(uint16_t n) {
	int count = 0;
	while(n) {
		++count;
		n = n & (n - 1);
	}
	return count;
}

Node *createNode(Node *parent, Node *child, int childindex,uint16_t groupid,uint16_t elpmap,
        vector<list<unsigned>>&subPartitions,unsigned vid, bool realNode){
    Node *tmp = new Node();
    tmp->parent = parent;
    if(childindex==-1){
        parent->children.push_back(tmp);
    }else{
        parent->children[childindex] = tmp;
    }
    tmp->groupid = groupid;
    tmp->elpmap = elpmap;
    tmp->elpNum = parent->elpNum+CountOnes(tmp->elpmap);
    if(child!=NULL){
        tmp->children.push_back(child);
        child->parent = tmp;
    }
    if(realNode){
        tmp->subPartID = subPartitions.size();
        list<unsigned> tmpv(1,vid);
        subPartitions.push_back(tmpv);
    }else{
        tmp->subPartID = -1;
    }
    return tmp;
}

void countvisit(uint16_t elpmap,uint16_t groupid, vector<unsigned> &visitedCount){
    for(int i=0;i<16;++i){
        int flag = (elpmap>>i) & 0x0001;
        if(flag==1){
            visitedCount[groupid*16+i] = visitedCount[groupid*16+i]+1;
        }
    }
}
//init_tree will generate the first tree structure for the basePartition, and meanwhile utilizes reordermap to delete
//reordered vertices from the basePartition
void init_tree(list<unsigned> &basePartition, map<unsigned,uint16_t> &curPartition, vector<list<unsigned>>&subPartitions,
    vector<unsigned>&reordermap,uint16_t mask, uint16_t groupid, Node *root, vector<unsigned> &visitedCount){
    root->parent = NULL;
    root->elpNum = 1;
    root->subPartID = 0;
    subPartitions.resize(1);
    list<unsigned> &rootvid = subPartitions[0];
    
    root->groupid = -1;
    Node *curnode = root;
    auto it = basePartition.begin();
    while(it!=basePartition.end()){
        unsigned vid = *it;
        //if the vid has been reordered, delete it from the partition
        if(reordermap[vid]!=0xffffffff){
            it = basePartition.erase(it);
            continue;
        }
        map<unsigned,uint16_t>::iterator ite = curPartition.find(vid);
        if(ite==curPartition.end()){
            rootvid.push_back(vid);
            it = basePartition.erase(it);
            continue; 
        }
        uint16_t elpmap = ite->second;
        elpmap = elpmap&mask;
        if(elpmap==0) { 
            rootvid.push_back(vid);
            it = basePartition.erase(it);
            continue; 
        }
        countvisit(elpmap,groupid,visitedCount);
        //this condition is not correct
        while(elpmap!=0){
            bool hasCommonELP = false;
            uint16_t matchedElp = 0;
            for(int i=0;i<curnode->children.size();++i){
                Node *child = curnode->children[i];
                uint16_t commonelp = (child->elpmap) & elpmap;
                if(child->groupid!=groupid || commonelp==0){ continue; }
                hasCommonELP = true;
                elpmap = (~commonelp)&elpmap;
                //all elps in elpmap are matched with elpmap of child
                //we do not need to create new node, we need to add this vid to the subpart of this child
                if(elpmap==0 && child->elpmap==commonelp){
                    if(child->subPartID==-1){
                        child->subPartID = subPartitions.size();
                        list<unsigned> tmpv;
                        subPartitions.push_back(tmpv);
                    }
                    subPartitions[child->subPartID].push_back(vid);
                    it = basePartition.erase(it);
                }
                //elpmap contains the child elpmap
                else if(elpmap!=0 && child->elpmap==commonelp){
                    curnode = child; 
                }
                //child's elpmap contains elps of vid
                else if(elpmap==0 && child->elpmap!=commonelp){
                    child->elpmap = (child->elpmap)&(~commonelp);
                    createNode(curnode,child,i,groupid,commonelp,subPartitions,vid,true);
                    it = basePartition.erase(it);
                }
                //child's elpmap contains portion elps of vid
                else{//elpmap!=0 && child->elpmap!=commonelp
                    child->elpmap = (child->elpmap)&(~commonelp);
                    Node *tmpn = createNode(curnode,child,i,groupid,commonelp,subPartitions,vid,false);
                    createNode(tmpn,NULL,-1,groupid,elpmap,subPartitions,vid,true);
                    elpmap = 0;
                    it = basePartition.erase(it);
                }
                break;
            }
            if(!hasCommonELP){
                createNode(curnode,NULL,-1,groupid,elpmap,subPartitions,vid,true);
                elpmap = 0;
                it = basePartition.erase(it);
            }
        }
    }
}

void genTree(Node *curnode,map<unsigned,uint16_t>&curPartition, vector<list<unsigned>>&subPartitions,
    uint16_t mask,uint16_t groupid){
    uint16_t commonelp=0;
    for(int i=0;i<curnode->children.size();++i){
        Node *tmp = curnode->children[i];
        commonelp = commonelp&(tmp->elpmap);
    }
    //first check if all children of curnode share the same elpmap, if so, we create a common node with the shared 
    //elpmap as the child of curnode. and then move original children of curnode to the children of common node
    //last, remove shared elpmap from all children of common node and delete the child if no elpmap left after deleting 
    //shared elpmap
    if(commonelp>0){
        Node *commNode = createNode(curnode,NULL,-1,groupid,commonelp,subPartitions,0,false);
        int childsneedprocess = curnode->children.size()-1;
        for(int i=0;i<childsneedprocess;++i){
            Node *tmp = curnode->children[i];
            uint16_t remainelp = tmp->elpmap & (~commonelp);
            if(remainelp==0 && tmp->subPartID==-1){
                for(int j=0;j<tmp->children.size();++j){
                    commNode->children.push_back(tmp->children[j]);
                    tmp->children[j]->parent = commNode;
                }
                delete tmp;
            }else if(remainelp==0 && tmp->subPartID>-1){
                if(commNode->subPartID==-1){
                    commNode->subPartID=tmp->subPartID;
                }else{
                    list<unsigned> &dstlist = subPartitions[commNode->subPartID];
                    list<unsigned> &srclist = subPartitions[tmp->subPartID];
                    dstlist.insert(dstlist.end(),srclist.begin(),srclist.end());
                    srclist.clear();
                }
                for(int j=0;j<tmp->children.size();++j){
                    commNode->children.push_back(tmp->children[j]);
                    tmp->children[j]->parent = commNode;
                }
                delete tmp;
            }else if(remainelp>0){
                tmp->elpmap = remainelp;
                tmp->parent = commNode;
                commNode->children.push_back(tmp);
            }
        }
        curnode->children.erase(curnode->children.begin(),curnode->children.end()-1);
    }
    if(curnode->subPartID>-1){
        //generate subtree of curnode based on its vids
        list<unsigned> &curpart = subPartitions[curnode->subPartID];
        auto ite=curpart.begin();
        while(ite!=curpart.end()){
            unsigned vid = *ite;
            map<unsigned,uint16_t>::iterator curite = curPartition.find(vid);
            if(curite==curPartition.end()){
                ++ite;
                continue; 
            }
            uint16_t elpmap = curite->second;
            elpmap = elpmap&mask;
            if(elpmap==0) { 
                ++ite;
                continue; 
            }
            while(elpmap!=0){
                bool hasCommonELP = false;
                uint16_t matchedElp = 0;
                for(int i=0;i<curnode->children.size();++i){
                    Node *child = curnode->children[i];
                    uint16_t commonelp = (child->elpmap) & elpmap;
                    if(child->groupid!=groupid || commonelp==0){ continue; }
                    hasCommonELP = true;
                    elpmap = (~commonelp)&elpmap;
                    if(elpmap==0 && child->elpmap==commonelp){
                        if(child->subPartID==-1){
                            child->subPartID = subPartitions.size();
                            list<unsigned> tmpv;
                            subPartitions.push_back(tmpv);
                        }
                        subPartitions[child->subPartID].push_back(vid);
                        ite = curpart.erase(ite);
                    }else if(elpmap!=0 && child->elpmap==commonelp){
                        curnode = child; 
                    }else if(elpmap==0 && child->elpmap!=commonelp){
                        child->elpmap = (child->elpmap)&(~commonelp);
                        createNode(curnode,child,i,groupid,commonelp,subPartitions,vid,true);
                        ite = curpart.erase(ite);
                    }else{//elpmap!=0 && child->elpmap!=commonelp
                        child->elpmap = (child->elpmap)&(~commonelp);
                        Node *tmpn = createNode(curnode,child,i,groupid,commonelp,subPartitions,vid,false);
                        createNode(tmpn,NULL,-1,groupid,elpmap,subPartitions,vid,true);
                        elpmap = 0;
                        ite = curpart.erase(ite);
                    }
                    break;
                }
                if(!hasCommonELP){
                    createNode(curnode,NULL,-1,groupid,elpmap,subPartitions,vid,true);
                    elpmap = 0;
                    ite = curpart.erase(ite);
                }
            }
        }
        if(curpart.size()>0) { return; }
        else curnode->subPartID = -1;
    }
    //if there is some vids left in curpart, we can not combine curnode with its child or parent
    //no vids left in curnode, and curnode has only one child, we can combine curnode with its child
    if(curnode->children.size()==1){
        if(curnode->groupid==groupid){
            curnode->children[0]->elpmap = curnode->children[0]->elpmap | curnode->elpmap;
        }
        curnode->children[0]->parent = curnode->parent;
        Node *p = curnode->parent;
        if(curnode->parent!=NULL){
            for(int i=0;i<p->children.size();++i){
                if(curnode==p->children[i]){
                    p->children[i] = curnode->children[0];
                    delete curnode;
                    curnode = p->children[i];
                    break;
                }
            }
        }else{
            Node *tmpn = curnode->children[0];
            delete curnode;
            curnode = tmpn;
        }
    }
}

void build_tree(map<unsigned,uint16_t> &curPartition, vector<list<unsigned>>&subPartitions,
    uint16_t mask, uint16_t groupid, Node *root){
    //build from leaf nodes
    vector<int> processedIndex;
    Node *curnode = root->children[0];
    int curindex = -1;
    processedIndex.push_back(curindex);
    while(curnode->parent!=NULL || curindex!=root->children.size()){
        curnode = curnode->parent;
        curindex = processedIndex.back();
        processedIndex.pop_back();
        curindex++;
        if(curindex==curnode->children.size()){
            genTree(curnode, curPartition, subPartitions,mask,groupid);
            continue;
        }
        while(curnode->children.size()!=0){
            curnode = curnode->children[curindex];
            processedIndex.push_back(curindex);
            curindex = 0;
        }
        genTree(curnode, curPartition, subPartitions,mask,groupid);
    }
}

class subPartElpNumClass{
public:
    int index;
    int elpnum;
    subPartElpNumClass(){
        index=0;
        elpnum=0;
    }
};
void delChildFromParent(Node *child){
    Node *parent = child->parent;
    if(parent!=NULL){
        for(int i=0;i<parent->children.size();++i){
            if(child==parent->children[i]){
                parent->children.erase(parent->children.begin()+i);
                break;
            }
        }
    }
}
int chooseChild(Node *curnode, vector<list<unsigned>> &subpartitions){
    vector<Node*> &children = curnode->children;
    int maxi=0,maxelpnum=0,maxvidnum=0;
    for(int i=0;i<children.size();++i){
        Node *child = children[i];
        if(child->elpNum > maxelpnum){
            maxelpnum = child->elpNum;
            maxi = i;
        }else if(subpartitions[child->subPartID].size()>maxvidnum){
            maxvidnum = subpartitions[child->subPartID].size();
            maxi = i;
        }
    }
    return maxi;
}
unsigned performReorder(Node *root,vector<list<unsigned> > &subPartitions,vector<Node*> &subPart2TreePos,
        vector<subPartElpNumClass> &subPartElpNum, vector<unsigned> &reordermap, unsigned reorderNum){
    int subpartindex=0, startSubPart;
    Node *curnode = NULL;
    while(true){
        while(curnode==NULL && subpartindex<subPartElpNum.size()){
            startSubPart = subPartElpNum[subpartindex].index;
            if(startSubPart==-1){
                subpartindex++;
                continue;
            }
            curnode = subPart2TreePos[startSubPart];
            subpartindex++;
        }
        if(curnode==NULL){
            break;
        }
        while(curnode->parent!=NULL){
            if(curnode->subPartID>-1){
                startSubPart = curnode->subPartID;
                subPart2TreePos[startSubPart] = NULL;
                subPartElpNum[startSubPart].index = -1;
                curnode->subPartID = -1;
                list<unsigned> &subpart = subPartitions[startSubPart];
                unsigned startvid = subpart.size()+reorderNum;
                for(auto ite=subpart.begin();ite!=subpart.end();++ite){
                    unsigned oldvid = *ite;
                    reordermap[oldvid] = startvid-1;
                    reorderNum++;
                    startvid--;
                }
            }
            if(curnode->children.size()==0){
                Node *tmp = curnode;
                delChildFromParent(curnode);
                delete curnode;
                curnode = tmp;
            }else{
                int childIndex = chooseChild(curnode,subPartitions);
                curnode = curnode->children[childIndex];
            }
        }
        curnode = NULL;
    }
    if(root->children.size()!=0){
        std::cout <<"wrong reorder, root should have no children"<<endl;
    }
    if(root->subPartID>-1){
        startSubPart = root->subPartID;
        subPart2TreePos[startSubPart] = NULL;
        subPartElpNum[startSubPart].index = -1;
        root->subPartID = -1;
        list<unsigned> &subpart = subPartitions[startSubPart];
        unsigned startvid = subpart.size()+reorderNum;
        for(auto ite=subpart.begin();ite!=subpart.end();++ite){
            unsigned oldvid = *ite;
            reordermap[oldvid] = startvid-1;
            reorderNum++;
            startvid--;
        }
    }
    delete root;
    return reorderNum;
}


int findMaxIndex(vector<list<unsigned>> &graphCopy, vector<unsigned> &visitedCount){
    unsigned max=0;
    int index=-1;
    for(int i=0;i<graphCopy.size();i++){
        unsigned size = graphCopy[i].size()-visitedCount[i];
        if(size>max){
            index=i;
            max = size;
        }
    }
    if(max==0){
        std::cout<<"do not find max index"<<endl;
    }
    return index;
}

void traveseTree(Node *root, vector<Node*> &subPart2TreePos, vector<subPartElpNumClass>&subPartElpNum){
    if(root->subPartID>-1){
        subPart2TreePos[root->subPartID] = root;
        subPartElpNum[root->subPartID].elpnum = root->elpNum;
        subPartElpNum[root->subPartID].index = root->subPartID;
    }
    if(root->children.size()==0){ return; }

    list<int> nextProcessIndex;
    Node *curnode = root;
    int nextChildIndex = 0;
    while(curnode!=NULL){
        //forward
        if(curnode->children.size()>0 && nextChildIndex!=curnode->children.size()){
            curnode = curnode->children[nextChildIndex];
            nextProcessIndex.push_back(nextChildIndex+1);
            nextChildIndex = 0;
            if(curnode->subPartID>-1){
                subPart2TreePos[curnode->subPartID] = curnode;
                subPartElpNum[curnode->subPartID].elpnum = curnode->elpNum;
                subPartElpNum[curnode->subPartID].index = curnode->subPartID;
            }
        }else{//backward
            nextChildIndex = nextProcessIndex.back();
            nextProcessIndex.pop_back();
            curnode = curnode->parent;
        }
    }
}
bool cmp(subPartElpNumClass a,subPartElpNumClass b){
    return a.elpnum > b.elpnum;
}
//graph[i] is the ith label partition, each partition is a map
//the key is the id of source vertex, and the value is a vector that contains
//neighbors of source vertex that comply the label.
/*TODO: we need to verify that, in a edge label partition,
 * if the length of contiguous part a is greater than the length of contiguous part b,
 * then the biggest vertex id in a is smaller than the smallest vertex id in b.
 **/
void genReorderMap(vector<map<unsigned,map<unsigned,vector<unsigned>>>> &graph,vector<unsigned> &reordermap){

    //in reorder, we do not need neighbors, therefore we use bitset<1> instead
    vector<list<unsigned>> graphCopy(graph.size());
    //record how many vids visited in each elp
    vector<unsigned> visitedCount(graph.size(),0);
    //vids in each 16 cosecutive edge label partitions are grouped together.
    //and associate each vid with the elp ids that contain this vid.
    //each bit represent one elp
    vector<map<unsigned,uint16_t>> elpsOfEachV((graph.size()+15)/16);
    cout<<"generating simplified data for label partitions"<<endl;
    for(int i=0;i<graph.size();++i){
        int groupID = i/16;
        int innerIndex = i%16;
        map<unsigned,uint16_t> &tmpG = elpsOfEachV[groupID];
        map<unsigned,map<unsigned,vector<unsigned> > > &tmpa = graph[i];
        list<unsigned> &tmplist = graphCopy[i];
        for(auto iteraa=tmpa.begin();iteraa !=tmpa.end();iteraa++){
            tmplist.push_back(iteraa->first);
            auto iteG=tmpG.find(iteraa->first);
            if(iteG!=tmpG.end()){
                iteG->second = (iteG->second)|(1<<innerIndex);
            }else{
                tmpG.insert(pair<unsigned,uint16_t>(iteraa->first,(1<<innerIndex)));
            }
        }
    }
    cout<<"generate simplified data done"<<endl;
    //sort edge label partitions by the number of source vertices the partition has in decreasing order
    //sort(graphCopy.begin(),graphCopy.end(),sortFunc);
    //each label labelPartition contains many vertices, our idea is
    //the more vertices in the labelPartition, the less contiguous subparts it contains
    //therefore, we sort labelPartitions based on the number of vertices it contains.
    //in each iteration, we reorder all vertices in this label partition
    unsigned totLabelPartition = graphCopy.size();
    unsigned reorderVNum = 0;
    uint16_t mask;
    for(unsigned ii=0;ii<totLabelPartition;++ii){
        cout<<"take label partition "<<ii<<" as the base label partition"<<endl;
        int maxIndex = findMaxIndex(graphCopy,visitedCount);
        if(maxIndex==-1){
            cout<<"all vertices have been processed"<<endl;
            break;
        }
        unsigned innerIndex = maxIndex%16;
        //basePartition is the labelPartition contains the most number of vertices
        //in each iteration, we reorder vertex ids for basePartition
        list<unsigned> &basePartition = graphCopy[maxIndex];
        //basePartition will be divided into sub-partitions that overlaps with other label partitions
        //each sub-partition contains contiguous vertices
        //the index of a sub-partition in subPartitions is the id of this sub-partition
        vector<list<unsigned> > subPartitions;
        Node *root = new Node();
        for(int i=0;i<elpsOfEachV.size();++i){
            if(maxIndex/16==i){ mask = ~(1<<innerIndex); }
            else{               mask = 0xffff; }
            if(i==0){   init_tree(basePartition, elpsOfEachV[i],subPartitions,reordermap,mask,i,root,visitedCount); }
            else{       build_tree(elpsOfEachV[i],subPartitions,mask,i,root); }
        }
        //now we need to travser the tree to peform reorder
        vector<Node*> subPart2TreePos(subPartitions.size(),NULL);
        vector<subPartElpNumClass> subPartElpNum(subPartitions.size());
        traveseTree(root,subPart2TreePos,subPartElpNum);
        sort(subPartElpNum.begin(),subPartElpNum.end(),cmp);
        reorderVNum = performReorder(root,subPartitions,subPart2TreePos,subPartElpNum,reordermap,reorderVNum);
        graphCopy[maxIndex].clear();
    }
}

void genNeigIndex(vector<uint> &neig){
    vector<uint> newneig;
    if(neig.size()<VBLOCKSIZE){
        return;
    }else if(neig.size()<=32*VBLOCKSIZE){
        uint blocknum = neig.size()/VBLOCKSIZE;
        for(uint i=1;i<=blocknum;i++){
            newneig.push_back(neig[i*VBLOCKSIZE-1]);
        }
        if(neig.size()%VBLOCKSIZE>0){
            newneig.push_back(neig[neig.size()-1]);
        }
        neig.insert(neig.begin(),newneig.begin(),newneig.end());
    }else{
        uint blocknum = neig.size()/32;
        for(uint i=1;i<=31;++i){
            newneig.push_back(neig[i*blocknum-1]);
        }
        newneig.push_back(neig[neig.size()-1]);
        neig.insert(neig.begin(),newneig.begin(),newneig.end());
    }
}
//data format for our interval index format
//uint0 uint1 uint2 uint3 uint4 array1 array2 array3 array4
//uint0: the number of uints in this label partition.
//uint1: ther number of source vertices (including blank vertices) in this partition
//uint2: position of interval vertices neighbor addr (array2) and the lenght of this interval and previous intervals,
//uint3: position of hash table index.
//uint4: position of neighbor data
//array1: boundries of interval index, at most has 256 entries,
//  each entry contains 2 uints, including start vid, prelen(the length of this interval and previous intervals),
//  loaded into shared memory.
//array2: interval vertices neighbor addr and one extra uint at the end of this section to record the end position of the last one
//array3: hash index,
//array4: neighbors
//subpartsinfo stores all contiguous subparts of this label partition
bool writeHybridDataStructure(vector<subPartInfo>&subpartsinfo, map<uint,map<uint,vector<uint> > >& newLabelPartition,
            ofstream &graph, ofstream &readableGraph,uint totNeigNum,labelInfo &label, uint &totWriteNum,map<uint,uint>&reorderVLabel){
    uint intervalNum = subpartsinfo.size();
    std::cout<<"intervalNum="<<intervalNum<<std::endl;
    /* if there are more than 1024 intervals, we use level index. each level index 256 intervals and use 32 level indexes at most.
     * if there are less than 1024 intervals, we just use previous storeage format.
     */
    uint totIntervalIndexNum=0;
    for(uint i=0;i<intervalNum;++i) { totIntervalIndexNum += subpartsinfo[i].len; }
    if(intervalNum<=1024){
        //sort(subpartsinfo.begin(),subpartsinfo.end(),[ ](subPartInfo &a, subPartInfo &b) { return a.len>b.len; });
        //sort(subpartsinfo.begin(),subpartsinfo.begin()+256,[ ](subPartInfo &a, subPartInfo &b) { return a.svid < b.svid; });
        //sort(subpartsinfo.begin(),subpartsinfo.end(),[ ](subPartInfo &a, subPartInfo &b) { return a.svid<b.svid; });
        uint totStoreNum = 5+intervalNum*2+1+1+totIntervalIndexNum+1+totNeigNum;
        uint totHashIndexNum = 0;
        uint *writePos = (uint*)calloc(totStoreNum,sizeof(uint));
        writePos[0] = totStoreNum;
        writePos[1] = totIntervalIndexNum;
        writePos[2] = intervalNum;
        writePos[3] = intervalNum*2+1+1+totIntervalIndexNum+1;
        writePos[4] = writePos[3]+totHashIndexNum*32;
        readableGraph<<"five indexs: "<<writePos[0]<<" "<<writePos[1]<<" "<<writePos[2]<<" "<<writePos[3]<<" "<<writePos[4]<<endl;
        uint intervalAddr = 5;
        uint intervalIndexAddr = 5+intervalNum*2+1+1;
        uint neigAddr = intervalIndexAddr+totIntervalIndexNum+1+totHashIndexNum*32;
        uint baseNeigAddr = neigAddr;
        uint preLen = 0;
        writePos[intervalIndexAddr+intervalNum] = 0;
        for(uint i=0;i<intervalNum;++i){
            writePos[intervalAddr+i] = subpartsinfo[i].svid;
            writePos[intervalAddr+i+intervalNum+1] = preLen+subpartsinfo[i].len;
            preLen = preLen+subpartsinfo[i].len;
            for(uint j=subpartsinfo[i].svid;j<=subpartsinfo[i].evid;++j){
                map<uint,vector<uint> > &neig = newLabelPartition[j];
                writePos[intervalIndexAddr] = neigAddr-baseNeigAddr;
                map<uint,vector<uint> >::iterator ite;
                uint k=0;
                for(ite=neig.begin();ite!=neig.end();++ite){
                    vector<uint> &vlabelneig = ite->second;
                    for(uint l=0;l<vlabelneig.size();++l){
                        writePos[neigAddr+k] = vlabelneig[l];
                        ++k;
                    }
                }
                neigAddr += k;
                intervalIndexAddr++;
            }
        }
	    std ::cout<<"write hash index"<<std::endl;
        writePos[intervalIndexAddr] = neigAddr-baseNeigAddr;
        vector<uint> v_count_in_group(totHashIndexNum,0);
        uint graph_group_num = 32*totHashIndexNum;
        uint hashAddr = writePos[3];
        /*for(uint i=intervalNum;i<subpartsinfo.size();++i){
            uint startvid = subpartsinfo[i].svid;
            uint endvid = subpartsinfo[i].evid;
            for(uint j=startvid;j<=endvid;++j){
                uint key = j;
                uint group_index = MurmurHash2(&key,4,HASHSEED)%totHashIndexNum;
                if(v_count_in_group[group_index]==16){
                    cout<<"we need another group"<<endl;
                }else{
                    uint stored = v_count_in_group[group_index];
                    writePos[hashAddr+group_index*32+stored*2+0] = key;
                    stored++;
                    if(stored==15){
                        writePos[hashAddr+group_index*32+stored*2+0] =  0xffffffff;
                        stored++;
                    }
                    v_count_in_group[group_index] = stored;
                }
            }
        }*/
        for(uint j=0;j<graph_group_num;j=j+2){
            if(writePos[hashAddr+j]==0){
            }else if(writePos[hashAddr+j]==0xffffffff){
                writePos[hashAddr+j+1] = neigAddr;
            }else{
                uint key = writePos[hashAddr+j];
                map<uint,vector<uint> > &neig = newLabelPartition[key];
                writePos[hashAddr+j+1] = neigAddr;
                map<uint,vector<uint> >::iterator ite;
                uint k=0;
                for(ite=neig.begin();ite!=neig.end();++ite){
                    vector<uint> &vlabelneig=ite->second;
                    for(uint l=0;l<neig.size();++l){
                        writePos[neigAddr+k] = vlabelneig[l];
                        ++k;
                    }
                }
                neigAddr += k;
            }
        }
        graph.write((char*)writePos,totStoreNum*sizeof(uint));
        readableGraph<<"interval index"<<endl<<"svid: ";
        for(uint i=0;i<intervalNum;++i){
            readableGraph << writePos[intervalAddr+i]<<" ";
        }
        readableGraph<<"interval prelen: ";
        for(uint i=0;i<intervalNum+1+1;++i){
            readableGraph<<writePos[intervalAddr+intervalNum+i]<<" ";
        }
        readableGraph<<endl;
        readableGraph<<"interval addr"<<endl;
        intervalIndexAddr = 5+intervalNum*2+1+1;
        for(uint i=0;i<totIntervalIndexNum+1;++i){
            readableGraph<<writePos[intervalIndexAddr+i]<<" ";
        }
        readableGraph<<endl;
        readableGraph<<"neigbors"<<endl;
        for(uint i=0;i<intervalNum;++i){
            for(uint j=subpartsinfo[i].svid;j<=subpartsinfo[i].evid;++j){
                readableGraph<<"label:"<<reorderVLabel[j]<<" svid:"<<j<<" ";
                map<uint,vector<uint> > &neig = newLabelPartition[j];
                map<uint,vector<uint> >::iterator ite;
                for(ite=neig.begin();ite!=neig.end();++ite){
                    uint evidlabel = ite->first;
                    readableGraph<<"evidlabel:"<<evidlabel<<" ";
                    readableGraph<<"neigs:{";
                    vector<uint> &vlabelneig = ite->second;
                    for(uint l=0;l<vlabelneig.size();++l){
                        readableGraph<<vlabelneig[l]<<" ";
                    }
                    readableGraph<<"} ";
                }
                readableGraph<<endl;
            }
        }
        readableGraph<<endl;
        free(writePos);
    }else{
        uint tmpsize = (intervalNum+31)/32;
        uint blocksize = (tmpsize+511)/512;
        blocksize = blocksize*32;
        uint intervalNum_512 = blocksize*512;
        uint totStoreNum = 5+513+intervalNum_512*2+1+1+totIntervalIndexNum+1+totNeigNum;
        uint *writePos = (uint*)calloc(totStoreNum,sizeof(uint));
        writePos[0] = totStoreNum;
        writePos[1] = totIntervalIndexNum;
        writePos[2] = intervalNum_512;
        writePos[3] = 513+intervalNum_512*2+1+1+totIntervalIndexNum+1;
        writePos[4] = blocksize;
        uint levelIntervalAddr = 5;
        uint intervalAddr = 5+513;
        uint intervalIndexAddr = 5+513+intervalNum_512*2+1+1;
        uint neigAddr = intervalIndexAddr+totIntervalIndexNum+1;
        uint baseNeigAddr = neigAddr;
        uint preLen = 0;
        writePos[intervalIndexAddr+intervalNum] = 0;
        uint tmpIndex=0;
        for(uint i=0;i<intervalNum_512;++i){
            if(i%blocksize==0){
                if(i<intervalNum){
                    writePos[levelIntervalAddr+tmpIndex] = subpartsinfo[i].svid;
                }else{
                    writePos[levelIntervalAddr+tmpIndex] = subpartsinfo[intervalNum-1].svid+subpartsinfo[intervalNum-1].len;
                }
                tmpIndex++;
            }
            //maybe we do not need this else if
            else if(i==intervalNum_512-1){
                writePos[levelIntervalAddr+tmpIndex] = subpartsinfo[intervalNum-1].svid+subpartsinfo[intervalNum-1].len;
            }
            if(i<intervalNum){
                writePos[intervalAddr+i] = subpartsinfo[i].svid;
                writePos[intervalAddr+i+intervalNum_512+1] = preLen+subpartsinfo[i].len;
                preLen = preLen+subpartsinfo[i].len;
                for(uint j=subpartsinfo[i].svid;j<=subpartsinfo[i].evid;++j){
                    map<uint,vector<uint> > &neig = newLabelPartition[j];
                    writePos[intervalIndexAddr] = neigAddr-baseNeigAddr;
                    map<uint,vector<uint> >::iterator ite;
                    uint k=0;
                    for(ite=neig.begin();ite!=neig.end();++ite){
                        vector<uint> &vlabelneig = ite->second;
                        for(uint l=0;l<vlabelneig.size();++l){
                            writePos[neigAddr+k] = vlabelneig[l];
                            ++k;
                        }
                    }
                    neigAddr += k;
                    intervalIndexAddr++;
                }
            }else{
                writePos[intervalAddr+i] = 0;
                writePos[intervalAddr+i+intervalNum_512+1] = preLen;
            }
        }
	    std ::cout<<"write hash index"<<std::endl;
        writePos[intervalIndexAddr] = neigAddr-baseNeigAddr;
        graph.write((char*)writePos,totStoreNum*sizeof(uint));
        readableGraph<<"interval index"<<endl<<"svid: ";
        for(uint i=0;i<intervalNum_512;++i){
            readableGraph << writePos[intervalAddr+i]<<" ";
        }
        readableGraph<<"interval prelen: ";
        for(uint i=0;i<intervalNum_512+1+1;++i){
            readableGraph<<writePos[intervalAddr+intervalNum_512+i]<<" ";
        }
        readableGraph<<endl;
        readableGraph<<"interval addr"<<endl;
        intervalIndexAddr = 5+intervalNum_512*2+1+1;
        for(uint i=0;i<totIntervalIndexNum+1;++i){
            readableGraph<<writePos[intervalIndexAddr+i]<<" ";
        }
        readableGraph<<endl;
        readableGraph<<"neigbors"<<endl;
        for(uint i=0;i<intervalNum;++i){
            for(uint j=subpartsinfo[i].svid;j<=subpartsinfo[i].evid;++j){
                readableGraph<<"label:"<<reorderVLabel[j]<<" svid:"<<j<<" ";
                map<uint,vector<uint> > &neig = newLabelPartition[j];
                map<uint,vector<uint> >::iterator ite;
                for(ite=neig.begin();ite!=neig.end();++ite){
                    uint evidlabel = ite->first;
                    readableGraph<<"evidlabel:"<<evidlabel<<" ";
                    readableGraph<<"neigs:{";
                    vector<uint> &vlabelneig = ite->second;
                    for(uint l=0;l<vlabelneig.size();++l){
                        readableGraph<<vlabelneig[l]<<" ";
                    }
                    readableGraph<<"} ";
                }
                readableGraph<<endl;
            }
        }
        readableGraph<<endl;
        free(writePos);
    }
    return true;
}

void addEdgeToGraphDebug(uint *e_info, map<uint,uint>&v_label){

    uint e_label = e_info[2];
    uint svid = e_info[0];
    uint evid = e_info[1];
    if(svid==evid){
        cout<<"wrong, equal vids"<<endl;
    }
    auto ite=v_label.find(svid);
    if(ite!=v_label.end()){
        v_label.erase(svid);
    }
    auto ite1=v_label.find(evid);
    if(ite1!=v_label.end()){
        v_label.erase(evid);
    }
}

void addEdgeToGraph(uint *e_info, vector<map<uint,map<uint,vector<uint> > > > &graph, 
    map<uint,uint>&v_label){

    uint e_label = e_info[2];
    uint svid = e_info[0];
    uint evid = e_info[1];
    uint evlabel = v_label[evid];
    map<uint,map<uint,vector<uint> > > &edgeLabelPart = graph[e_label];
    map<uint,map<uint,vector<uint> > >::iterator ite = edgeLabelPart.find(svid);
    if(ite==edgeLabelPart.end()){
        vector<uint> tmp;
        tmp.push_back(evid);
        map<uint, vector<uint> > tmpmap;
        tmpmap.insert(pair<uint,vector<uint> >(evlabel,tmp));
        edgeLabelPart.insert(pair<uint,map<uint,vector<uint> > >(svid,tmpmap));
    }else{
        map<uint,vector<uint> >&tmpmap = ite->second;
        map<uint,vector<uint> >::iterator itea = tmpmap.find(evlabel);
        if(itea==tmpmap.end()){
            vector<uint> tmp;
            tmp.push_back(evid);
            tmpmap.insert(pair<uint,vector<uint> >(evlabel,tmp));
        }else{
            vector<uint> &tmp = itea->second;
            bool found = false;
            for(uint i=0;i<tmp.size();++i){
                if(tmp[i]==evid){
                    found = true;
                    break;
                }
            }
            if(!found){
                tmp.push_back(evid);
            }
        }
    }
    svid = e_info[1];
    evid = e_info[0];
    evlabel = v_label[evid];
    ite = edgeLabelPart.find(svid);
    if(ite==edgeLabelPart.end()){
        vector<uint> tmp;
        tmp.push_back(evid);
        map<uint, vector<uint> > tmpmap;
        tmpmap.insert(pair<uint,vector<uint> >(evlabel,tmp));
        edgeLabelPart.insert(pair<uint,map<uint,vector<uint> > >(svid,tmpmap));
    }else{
        map<uint,vector<uint> >&tmpmap = ite->second;
        map<uint,vector<uint> >::iterator itea = tmpmap.find(evlabel);
        if(itea==tmpmap.end()){
            vector<uint> tmp;
            tmp.push_back(evid);
            tmpmap.insert(pair<uint,vector<uint> >(evlabel,tmp));
        }else{
            vector<uint> &tmp = itea->second;
            bool found = false;
            for(uint i=0;i<tmp.size();++i){
                if(tmp[i]==evid){
                    found = true;
                    break;
                }
            }
            if(!found){
                tmp.push_back(evid);
            }
        }
    }
}

unsigned genSubParts(vector<subPartInfo> &subpartsinfo,map<unsigned,map<unsigned,vector<unsigned> > > &labelPartition){
    if(labelPartition.size()==0){
        return 0;
    }
    map<unsigned,map<unsigned,vector<unsigned> > >::iterator itera=labelPartition.begin();
    unsigned totv = labelPartition.size();
    unsigned curvid = itera->first;
    unsigned previd = itera->first;
    unsigned start = previd;
    unsigned tmpPreLen=0;
    unsigned totNeigNum=0;
    map<unsigned,vector<unsigned> >::iterator ite;
    map<unsigned,vector<unsigned> >&vneig = itera->second;
    for(ite=vneig.begin();ite!=vneig.end();++ite){
        totNeigNum += ite->second.size();
    }
    itera++;
    while(itera != labelPartition.end()){
        curvid = itera->first;
        map<unsigned,vector<unsigned> >&vneig = itera->second;
        for(ite=vneig.begin();ite!=vneig.end();++ite){
            totNeigNum += ite->second.size();
        }
        if(curvid==previd+1){
            previd = curvid;
        }else if(curvid>previd+1){
            subPartInfo tmpinfo;
            tmpinfo.svid = start;
            tmpinfo.evid = previd;
            tmpinfo.prelen = tmpPreLen;
            tmpinfo.len = previd-start+1;
            //tmp.index = sortsubparts.size();
            subpartsinfo.push_back(tmpinfo);
            tmpPreLen= tmpPreLen+previd-start+1;
            start=curvid;
            previd=curvid;
        }else{
            cout << "wrong in "<< __FUNCTION__ << " line: "<< __LINE__ <<endl;
        }
        itera++;
    }
    subPartInfo tmpinfo;
    tmpinfo.svid = start;
    tmpinfo.evid = previd;
    tmpinfo.prelen = tmpPreLen;
    tmpinfo.len = previd-start+1;
    subpartsinfo.push_back(tmpinfo);
    return totNeigNum;
}

void genReorderGraph(vector<map<uint,map<uint,vector<uint> > > > &graph,vector<map<uint,map<uint,vector<uint> > > > &reorderGraph,
                        map<uint,uint>&reordermap){
    for(uint i=0;i<graph.size();++i){
        map<uint,map<uint,vector<uint> > >::iterator itera;
        map<uint,map<uint,vector<uint> > > &tmpPartition = graph[i];
        map<uint,map<uint,vector<uint> > > newmap;
        for(itera=tmpPartition.begin();itera != tmpPartition.end();itera++){
            uint orisvid = itera->first;
            uint newsvid = reordermap[orisvid];
            map<uint,vector<uint> > &orimap = itera->second;
            map<uint,vector<uint> >::iterator ite;
            map<uint,vector<uint> > tmpmap;
            for(ite=orimap.begin();ite!=orimap.end();ite++) {
                uint orievidlabel = ite->first;
                uint newevidlabel = orievidlabel;
                vector<uint> &orivec = ite->second;
                vector<uint> newvec;
                for (uint j = 0; j < orivec.size(); ++j) {
                    uint newvid = reordermap[orivec[j]];
                    newvec.push_back(newvid);
                }
                sort(newvec.begin(), newvec.end(), sortFuncUINT);
                if (newvec.size() > VBLOCKSIZE) {
                    genNeigIndex(newvec);
                }
                tmpmap.insert(pair<uint, vector<uint>>(newevidlabel, newvec));
            }
            newmap.insert(pair<uint,map<uint,vector<uint> > >(newsvid,tmpmap));
        }
        reorderGraph.push_back(newmap);
    }
}

//for now, we consider labeld graph
//and then stores only one copy of this part
int main(int argc, char* argv[]){
    unsigned v_num=0, e_num=0;
    string path = string(argv[1])+"/";//direcotry that contains the *.g file
    string baseFileName = string(argv[2]);//the base name of the *.g file
    //string path = "/home/lgz/projects/clion/";
    ifstream input(path+baseFileName+".g",std::ios::in);
    ofstream output(path+baseFileName+".mygraph",std::ios::binary|std::ios::out);
    if(!input.is_open()){
        cout<<"open "<<baseFileName+".g"<<" is wrong"<<endl;
        return 1;
    }
    if(!output.is_open()){
        cout<<"open "<<baseFileName+".mygraph"<<" is wrong"<<endl;
        return 1;
    }
    map<unsigned,unsigned> v_label;
    string line;
    while(getline(input,line)){
        if(line.length()==0){ continue; }
        if(line[0]=='t'){ continue; }
        if(line[0]=='v'){ 
            extractUINT(line,v_label,v_num);
        }
        else if(line[0]=='e'){ break; }
    }
    std::cout<<"reading vertices="<<v_num<<" "<<v_label.size()<<endl;
    //v_num = v_label.size();
    //map<v-e-v label, map<source vertex, neighbors>>
    vector<map<unsigned,map<unsigned,vector<unsigned> > > > graph;
    vector<labelInfo> labels;
    //map<string,uint> idtolabel;
    unsigned label_count=0;
    while(true){
        if(line[0]=='e'){
            uint e_info[3];
            extractEUINT(line,e_info);
            if(e_info[2]+1>graph.size()){
                graph.resize(e_info[2]+1);
            }
            addEdgeToGraph(e_info, graph, v_label);
            //addEdgeToGraphDebug(e_info, v_label);
        }
        if(!getline(input,line)){
            break;
        }
    }
    input.close();
    std::cout<<"reading data done: "<< graph.size()<<endl;
    //index: old vid, value: new vid
    vector<unsigned> reordermap(v_num,0xffffffff);
    //construct reorder map
    genReorderMap(graph,reordermap);
    map<unsigned,unsigned> reorderVLabel;
    for(auto ite=reordermap.begin();ite!=reordermap.end();++ite){
        unsigned oldvid = ite->first;
        unsigned newvid = ite->second;
        unsigned vidlabel = v_label[oldvid];
        reorderVLabel[newvid] = vidlabel;
    }
    cout<<"generate reorder map done: "<<reordermap.size()<<endl;
    //use reorder map to build new label graph
    vector<map<unsigned,map<unsigned,vector<unsigned> > > > reorderGraph;
    genReorderGraph(graph,reorderGraph,reordermap);
    cout<<"generate reorder graph done"<<endl;

    ofstream reordergraphfile(path+baseFileName+".reorder",std::ios::out);
    reordergraphfile<<reorderGraph.size()<<std::endl;
    for(unsigned i=0;i<reorderGraph.size();++i){
        map<unsigned,map<unsigned,vector<unsigned>>> &tmplabelpart = reorderGraph[i];
        reordergraphfile<<tmplabelpart.size()<<std::endl;
        for(auto ite = tmplabelpart.begin();ite!=tmplabelpart.end();++ite){
            unsigned svid = ite->first;
            map<unsigned,vector<unsigned>> &neigs = ite->second;
            reordergraphfile<<svid<<" "<<neigs.size()<<std::endl;
            for(auto ite1 = neigs.begin();ite1!=neigs.end();++ite1){
                unsigned evidlabel = ite1->first;
                vector<unsigned> &labelneigs = ite1->second;
                reordergraphfile<<evidlabel<<" "<<labelneigs.size()<<std::endl;
                for(unsigned j=0;j<labelneigs.size();++j){
                    reordergraphfile<<labelneigs[j]<<" ";
                }
                reordergraphfile<<std::endl;
            }
        }
    }
    reordergraphfile.close();
	std::cout<<"write readableGraph"<<std::endl;
    ofstream readableGraph(path+baseFileName+".readableGraph",std::ios::out);
    //output readable graph

    uint totWriteNum = 0;
    //construct index section for each graph and write all data to binary file
    //ofstream test("genraw.txt",std::ios::out);
    //test<<reorderGraph.size()<<endl;
    //sort(reorderGraph.begin(),reorderGraph.end(),sortFuncReorder);
    uint totpart = reorderGraph.size();
	std::cout<<"totpart="<<totpart<<std::endl;
    output.write((char*)(&totpart),4);
    for(uint i=0;i<reorderGraph.size();++i){
        vector<subPartInfo> subpartsinfo;
        uint totNeigNum = genSubParts(subpartsinfo,reorderGraph[i]);
        if(subpartsinfo.size()==0){
            std::cout<<"0 size partition found"<<std::endl;
            uint zero = 0;
            output.write((char*)(&zero),4);
            continue;
        }
        readableGraph<<"edge label: "<< i <<endl;
	    std::cout<<"write edge label: "<< i <<std::endl;
        //write data to binary file
        bool isWrite = writeHybridDataStructure(subpartsinfo,reorderGraph[i], output,readableGraph,totNeigNum,labels[i],totWriteNum,reorderVLabel);
        if(!isWrite){
            uint zero = 0;
            output.write((char*)(&zero),4);
        }
    }
	readableGraph.close();
	std::cout<<"write metadata file"<<std::endl;
    //test.close();
    ofstream meta(path+baseFileName+".metadata",ios::out);
    map<uint,uint>::iterator iter;
    for(iter=reordermap.begin();iter!=reordermap.end();iter++){
        //new id, label, old id
        meta<<iter->second<<" "<<v_label[iter->first] <<" "<< iter->first<<endl;
    }
    meta.close();
	std::cout<<"write metadata file done"<<std::endl;
    input.close();
    output.close();
    return 0;
}
